Information exchanges via a network include list matching, in which only a common part among lists held by two or more participants is computed and extracted. A specific application of the list matching is a match making service, in which the list matching is performed on a database (list) describing a profile of a member including an interest, and members having common interests are introduced to each other. Besides, the list matching may be utilized by a plurality of financial institutes to query a list of specific users (black list, for example) to find users listed by the plurality of financial institutes.
Recently, as the network environment, such as Internet, has become widespread, privacy protection on the network has become more important, and thus, the list matching has become required to extract the common part without disclosing the contents of the list held by each participant.
In the past, to implement the list matching on the network, there has been a method of providing a TTP (Trusted Third Party) server to manage the lists to be subject to the list matching and compute the common part on the TTP server. In this case, the list information confidentiality depends on the security of the TTP server.
In addition, a peer-to-peer service not requiring a specific server has become widespread recently, and thus, the list matching may be performed without the TTP server. In order to ensure the security in such a case, there is disclosed a protocol involving a cryptography referred to as an oblivious polynomial evaluation (OPE) in the following Literature 1.
Literature 1: Naor, M. and Pinkas, B, “Oblivious Transfer and Polynomial Evaluation,” in proc. of STOC, 1999.
In Literature 1, there is described the following protocol:
It is assumed that Alice and Bob, the list holders, have list AL={a1, . . . , an} and BL={b1, . . . , bn}, respectively;
1. Alice and Bob prepare nth order polynomials PA(x) and PB(x), respectively, in secret;
2. Alice uses the OPE to compute [PB(ai)]i=1n, and Bob also uses the OPE to compute [PA(bi)]i=1n; and
3. Alice opens [PA(ai)+PB(ai)]i=1n, and Bob opens [PA(bi)+PB(bi)]i=1n.
According to this method, with respect to a known item in a list, a third party cannot estimate the presence or absence of the common item in another list.
As described above, in the case of the information exchange through the list matching, if the system includes the TTP server to manage the list to be subject to the list matching, the list information confidentiality depends on the security of the TTP server. Therefore, if the security of the TTP server is broken, confidential information in the list will be leaked.
Besides, according to the protocol involving the OPE used for the peer-to-peer list matching disclosed in Literature 1, it is possible to prevent a third party from, with respect to a known item in a list, estimating the presence or absence of the common item in another list. However, one list holder can falsify an open value to make the other list holder believe in a mismatch, while he/she exclusively knowing the common part with the other.
Besides, methods for performing computation with an argument kept in secret among a plurality of parties and extracting the computation result for the argument include a method referred to as a distributed secret computation (multiparty protocol). The protocol involving the OPE is also included in the distributed secret computation. The distributed secret computation is described in, for example, the following Literature 2.
Literature 2: Ben-Or, Goldwasser, and Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation,” STOC, ACM, 1988.
To extract a common part from a plurality of lists by means of list matching, a comparison computation for each item is essential. Thus, for two lists each containing n items, n2 comparison computations are needed. Such a comparison computation can be easily programmed.
However, the distributed secret computation essentially involves addition and multiplication of two values, and therefore, it is difficult to include therein a branch instruction or the like required for the comparison computation. Thus, the peer-to-peer list matching using the distributed secret computation has been difficult in terms of efficiency in processing.